#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h" // Fernbedienung

#include <LEDA/core/queue.h>
#include <LEDA/core/tuple.h>
#include <LEDA/core/stack.h>

using namespace leda;


void topsort(node v, list<node>& sorted_list,stack<node>& backtrack,
		graph &g, GraphWin &gw, node_array<int> &marker, int &counter,bool &cycle_found) {

    edge e;

	//node already visited, cycle found, setting nodes from cycle color to red
	if (marker[v] == 0) {
		//start backtracking to find a potential cycle
		stack<node> swap;
		node back;
		//pop nodes until we reach the end of the stack or find v. and set the nodes color to red
		while (!backtrack.empty() && back != v) {
			back = backtrack.pop();
			swap.push(back);
			gw.set_color(back , red);
		}
		cycle_found = true;

		return;
	}

	//add current node to backtracking stack
	backtrack.push(v);

    // mark node as currently active
    marker[v] = 0;
    // color node green
    gw.set_color(v, green);
    control_wait(0.5);

    forall_out_edges(e, v) {
        node w = g.opposite(v, e);
        //if this node is new (or part of a loop) we continue
        if (marker[w] != 1){
        	gw.set_color(e,green);
          	topsort(w, sorted_list, backtrack, g, gw, marker, counter, cycle_found);
        }
        //if we found a cycle we want to exit the algorithm.
        if (cycle_found)
        	return;

    }
    //coming back from dfs, adding node to sorted list.
    sorted_list.append(v);
    gw.set_user_label(v,string("%d",counter--));
    //recolor the node and outgoing edges.
    gw.set_color(v, blue);
    forall_out_edges(e,v)
    {
    	gw.set_color(e,blue);
    }
    //mark node as no longer active (there can not be any loop here!)
    marker[v] = 1;
    //take the finished node out of the backtracking stack
    backtrack.pop();

    control_wait(0.5);

}


int main(int argc, char *argv[]) {

    GraphWin gw(800, 600);
    gw.display();
    create_control();
    gw.set_directed(false);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close(); destroy_control();
        exit(1);
    }

    /* Variables */
    list<node> sorted_list; 		// list with the sorted nodes
    list<node> no_inc_edges_list;	// list with nodes without incoming edges
    stack<node> backtrack;
    node_array<int> marker(g, -1);
    int counter;
    node v;
    edge e;
    bool cycle_found  = false;

    /* Set all the nodes to red, and the edges to yellow
     * eventually only the edges without incoming edges will remain red
     * the others will be changed to yellow
     */
    forall_nodes(v, g) {
        gw.set_label_type(v, user_label);
        gw.set_color(v,red);
    }
    forall_edges(e, g){
        gw.set_color(e, yellow);
    }

    /* Initializing the no_inc_edges_list with all the edges
     * then removing the ones with incoming edges,
     * hence remaining only the ones without incoming edges
     */
    no_inc_edges_list = g.all_nodes();
    forall_nodes(v,g) {
    	forall_in_edges(e,v) {
    	    	gw.set_color(v,yellow);
    	    	no_inc_edges_list.remove(v);
    	    }
    }
    control_wait(1);

    counter = g.number_of_nodes(); //initialize counter with the number of nodes from the graph

    /* For each node from no_inc_edges_list call 'topsort'*/
    while (!no_inc_edges_list.empty() && !cycle_found) {
    	node v = no_inc_edges_list.pop();
    	topsort(v, sorted_list, backtrack, g, gw, marker, counter, cycle_found);
    }

    gw.update_graph();
    // Acknowledge in case of cycle
    if (cycle_found) {
    	gw.acknowledge("Cycle found! Stopped algorithm!");
    } else {
    	gw.acknowledge("Ready!");
    }

    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
